Generally, in classical PKI architectures, devices like smart cards, tokens, USB keys or any other portable device, are advantageously able to internally generate RSA key pairs (public/private key). Such key pairs are used for the creation or verification of digital signatures.
Using independent portable devices is advantageous on a security point of view as such support provides a hardware protection. Private key used for the signature generation remains stored in the device's memory without any exposure to hackers.
RSA On Board Key Generation (OBKG) is thus a successful functionality in such architectures. Many dedicated APIs are proposed, for example by Javacard, to provide this functionality for applications implemented inside or outside the device.
However, this functionality faces a major drawback: calculation duration to generate a key pair is time consuming, sometimes several tens of seconds, and indeterminist.
RSA Key pair generation is primarily based on a pair of prime numbers generation, classically referenced as p and q. Their product constitutes the modulus which is associated to both key public and private. The prime number generation is the more time consuming step during key pair generation. Other steps are performed in a shortest and deterministic time.
Prime number generation is an iterative calculation from an initial random number and converging through successive derivations towards a prime number. Each iteration ends in a primality test and the loop stops when test is positive. Initial number being random, the number of iterations to perform varies in a non predictable way.
FIG. 1 schematically shows an iterative process as used in the prior art to generate a prime number.
In a first step S1, a random number is generated by a random number generator RNG. This random number constitutes a start point ps. This start point is then used in a derivation step S2. This derivation step S2, outputs candidate pc which is submitted to a primary test PT in a step S3.
If the primality test PT is negative (case N), the candidate pc is input to the derivation step S2 which will give another candidate. Iteratively, the process thus converges towards a prime number. This part of the process is probabilistic.
It is necessary to derive two prime numbers to generate a pair of keys. It is thus necessary to perform the iterative derivation process twice in order to obtain a pair of prime numbers. The process shown on FIG. 1 is thus repeated two times. Then a key generation based on the two prime numbers is performed. The duration of this last process is of constant duration.
However to generate a key pair, the calculation time can vary in large proportions. If the iterative loop quickly converges, the key pair can be in short time generated. Contrarily, if the generation of at least one of the two prime numbers requires a high number of iterations, the key pair generation can exceed admissible durations.
Thus, algorithms generally give an average run duration deduced from a large number of generations and depending from the device characteristics. However no maximal time can be guaranteed and large durations could be observed. Such duration can become too large for some requesting applications authorizing a limited processing time to the card.
Above this time limit, generation is considered as defective. The failure proportion is a function of the statistical distribution of the calculation time.
Alternative implementations enable to reduce the width of the distribution. A solution called On the Fly PK (Off-line/On-line Generation of RSA Keys with Smart Cards by N.Feyt, M Joye, D. Naccache, and P. Pallier, published in S.-P. Shieh, Ed., 2nd International Workshop for Asian Public Key infrastructures, pp. 153-158, Taipei, Taiwan, Oct. 30-Nov. 1, 2002) proposed to store on the card a predefined number of seeds enabling a very short and deterministic calculation of corresponding prime numbers requested for key generation.
This solution is however difficult to implement due, among others, to the constraints during the card production. Another major drawback is the limited generation number as this number directly depends on the number of stored seeds.
Another possibility to control the generation duration is interruptible OBKG interruptible which consists to interrupt calculations when a critical time is reached and to store the current intermediary context. The requesting application is asked through a specific return code to later pursue the calculation. Such a solution implies constraints that are potentially not admissible for the application.
Further alternative and advantageous solutions would, accordingly, be desirable in the art.